package com.hqq.exercise.stack_queue;

import java.util.Stack;

/**
 * JudgeStackOrder 判断栈的弹出序列
 * 题目描述:
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。
 * 输入样例:
 * {1、2、3、4、5}
 * {4、5、3、2、1}
 * <p>
 * {1、2、3、4、5}
 * {4、3、5、1、2}
 * 输出样例:
 * true
 * false
 * Created by heqianqian on 2017/8/13.
 */
public class JudgeStackOrder {

    /**
     * 判断一个栈的出栈序列是否是一个栈的入栈序列
     *
     * @param input  入栈序列
     * @param output 出栈序列
     * @return
     */
    public static boolean judgeStackOrder(int[] input, int[] output) {
        if (input == null || output == null) {
            throw new RuntimeException("序列为空!");
        }
        //使用辅助栈进行判断
        int pushCount = 0;
        Stack<Integer> stack = new Stack<>();
        //1 2 3 4 5
        //4、5、3、2、1
        //4、3、5、1、2
        for (int i = 0; i < output.length; i++) {
            //根据出栈序列压栈
            int expect = output[i];
            //如果元素位于栈顶 则可以直接被弹出
            if (!stack.isEmpty() && stack.peek() == expect) {
                stack.pop();
            } else {
                if (pushCount == input.length) {//所有元素都已入栈
                    return false;
                } else {
                    //否则把该元素和之前的元素先入栈
                    do {
                        stack.push(input[pushCount++]);
                    } while (stack.peek() != expect && pushCount < input.length);
                    if (stack.peek() == expect) {
                        stack.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }

}
